/* 
 * File:   BNode.cpp
 * Author: hamed
 * 
 * Created on November 23, 2010, 12:28 AM
 */

#include <stdlib.h>

#include "BNode.h"
#include "Minimizer.h"

BNode::BNode(int varNum){
    this->varNum = varNum;
    tuple = new TupleK(varNum);
    tupleInherit = new TupleK(varNum);
    gFunc = new TupleK(varNum);
    nodeName = "";
    operation = logic_or;
    childL=NULL;
    childR=NULL;
    isMinimized = false;
    gFuncStr = new string("");
    funcStr = new string("");
    gStrEmpty = true;
    fUpdated = false;
}

BNode::BNode(const BNode& orig) {
}

BNode::~BNode() {
    delete childL;
    delete childR;
    delete nodeName;
}
void BNode::SetChildL(BNode* childL) {
    this->childL = childL;
    this->childL->SetParent(this);
}
BNode* BNode::GetChildL() const {
    return childL;
}
void BNode::SetChildR(BNode* childR) {
    this->childR = childR;
    this->childR->SetParent(this);
}
BNode* BNode::GetChildR() const {
    return childR;
}
void BNode::SetParent(BNode* parent) {
    this->parent = parent;
}
BNode* BNode::GetParent() const {
    return parent;
}
TupleK* BNode::GetTuple() const{
    return tuple;
}
TupleK* BNode::GetTupleInherited() const{
    return tupleInherit;
}
void BNode::SetTuple(TupleK* tuple) {
    this->tuple = tuple;
}
void BNode::SetNodeName(const char* nodeName) {
    this->nodeName = nodeName;
}
const char* BNode::GetNodeName() const {
    return nodeName;
}

bool BNode::hasChildL(){
    if(childL != NULL)
        return true;
    else
        return false;
}

bool BNode::hasChildR(){
    if(childR != NULL)
        return true;
    else
        return false;
}

bool BNode::isLeaf(){
    if(childL == NULL && childR == NULL)
        return true;
    else
        return false;
}
void BNode::removeChildL(){
//    childL->~BNode();
    childL = NULL;
    delete childL;
}
void BNode::removeChildR(){
//    delete childR;
//    childR->~BNode();
    childR = NULL;
//    delete childR;
}
void BNode::removeChildren(){
    removeChildL();
    removeChildR();
}

void BNode::SetIsMinimized(bool isMinimized) {
    this->isMinimized = isMinimized;
}
bool BNode::IsIsMinimized() const {
    return isMinimized;
}
void BNode::SetGFunc(TupleK* gFunc) {
    this->gFunc = gFunc;
}
TupleK* BNode::GetGFunc() const {
    return gFunc;
}

void BNode::setFUpdated(bool updated){
    fUpdated = updated;
}

void BNode::process0(TupleK** tupleList, int len){
//     cout << "Calling P0: " << varNum << ", listLen: "<< len<< endl;
    int* comCounterEx = new int[varNum];
    bool* markingEx = new bool[varNum];
    int dominator=0, temp=0;
    int listLenL=0;
    int listLenR=0;
    LogicValue value;

//    ==========================================================================
//    FINDS THE COMMON VALUE BITS AND DOMINATING BIT POSITION
//    ==========================================================================
    for(int i=varNum-1; i>=0;i--){
        comCounterEx[i]=0;
        if(tupleList[0]->GetValueAt(i) == logic_invalid){
            continue;
        }
        for(int j=0; j< len; j++){
            if(tupleList[j]->GetValueAt(i) == tupleList[0]->GetValueAt(i))
                comCounterEx[i]++;
        }
        if(comCounterEx[i]>temp){
            temp=comCounterEx[i];
            dominator = i;
        }
    }
    
//    ==========================================================================
//    CALCULATES THE CUBE REPRESENTING THIS NODE TOWARDS THE LEAVES
//    ==========================================================================
    for(int i=dominator, n=0; i>=0;i--){
        markingEx[i] = false;
        if(tupleList[0]->GetValueAt(i) == logic_invalid){
            continue;
        }
        if(comCounterEx[dominator] == comCounterEx[i]){
            markingEx[i] = true;
            value = tupleList[0]->GetValueAt(i);
        }
        else{
            value = logic_invalid;
        }
        this->GetTuple()->SetValueAt(i,value);
//        ======================================================================
//        ADDED TO OPTIMIZE!
//        CALCULATES THE LIST LENGTH FOR THE CHILD NODES
//        ======================================================================
        //int n=0;
        if(markingEx[i]==false){
            while(n<len){
                if(tupleList[n]->GetValueAt(i)==logic_0){
                    listLenL++;
                }
                else if(tupleList[n]->GetValueAt(i)==logic_1){
                    listLenR++;
                }
                n++;
            }
        }
//        this->GetSubFunction()->SetValueAt(i,value);
    }
//    this->GetTuple()->print();

    tupleInherit->setTuple(tuple);
    int i=tupleInherit->GetTupleLength()-1;
    int gLen = gFunc->GetTupleLength();
    int invCounter=0, power2=0;
    int startBase=0, endBound=gLen;
    while(tuple->GetValueAt(i--) == logic_invalid);
    
    for(int j=i;j>=0;j--){
        if(parent->GetTupleInherited()->GetValueAt(j) != logic_invalid){
            tupleInherit->SetValueAt(j,parent->GetTupleInherited()->GetValueAt(j));
        }
    }
    while(i>0 && parent->GetTupleInherited()->GetValueAt(i--) != logic_invalid);
    i++;
//    cout <<i << ": ";tupleInherit->print();
    int copyStep = gLen>>1;
    int copyStepTemp = gLen>>1;
    int copyLen = gLen;
    
    for(;i>=0;i--){
        gLen>>=1;
        power2 = (1<<i);
        if(tupleInherit->GetValueAt(i) == logic_0){
            endBound -= gLen;
            copyStep = copyStepTemp;
            copyLen = gLen;

        }
        else if(tupleInherit->GetValueAt(i) == logic_1){
            startBase += gLen;
            copyStep = copyStepTemp;
            copyLen = gLen;
        }
        else if(tupleInherit->GetValueAt(i) == logic_invalid){
            invCounter++;
            copyStepTemp=gLen;
        }
    }
//    cout << "invCounter: " << invCounter << endl;
    if(gFunc->GetTupleLength() != (1<<invCounter)){
        TupleK* newG = new TupleK(1<<invCounter);
//        cout << startBase<<":"<<endBound<<":"<<copyLen<<":"<<copyStep<<":"<< endl;
        int j=newG->GetTupleLength()-1, neg=gFunc->GetTupleLength()-1;
        i=startBase;
        int g=i;
        while(g<endBound){
            g=i;
            for(;g<i+copyLen;g++){
                newG->SetValueAt(j--,gFunc->GetValueAt(neg-g));
//                cout <<g<<",";
            }
            i+=copyStep;
//            cout <<i<<",";
        }
//        cout << endl;
//        this->gFunc->print();
        this->gFunc = newG;
//        this->gFunc->print();
//        cout << "------------------------------------------------------"<< endl;
    }
//    ==========================================================================
//    IF THE G-FUNCTION IS ALL ONE, IT MEANS THE FUNCTION REPRESENTING THIS
//    SUB-TREE IS CONSTANT 1. OMITTING THE CREATION OF SUB-TREE!
//    ==========================================================================
//    cout << nodeName<< ": "; gFunc->print();
    if(gFunc->isAllOne()){
//        cout << nodeName<< ": returning\n";
        return;
    }
    
//    ==========================================================================
//    CREATES TWO LISTS CONTATING THE TWO SETS OF FUNCTIONS
//    FROM THIS NODE TOWARDS THE LEAVES
//    ==========================================================================
    TupleK** tupleL = new TupleK*[listLenL];
    TupleK** tupleR = new TupleK*[listLenR];

//    ==========================================================================
//    FILLS THE LEFT SIDE LIST WITH RESPECTING VALUES
//    ==========================================================================
    for(int i=0; i< listLenL; i++){
        tupleL[i] = new TupleK(varNum);
        for(int j=varNum-1; j>=0; j--){
            if(markingEx[j]==true){
                value = logic_invalid;
            }
            else{
                value = tupleList[i]->GetValueAt(j);
            }
            tupleL[i]->SetValueAt(j,value);
        }
//        tupleL[i]->print();
    }

//    ==========================================================================
//    FILLS THE RIGHT SIDE LIST WITH RESPECTING VALUES
//    ==========================================================================
    for(int i=0; i< listLenR; i++){
        tupleR[i] = new TupleK(varNum);
        for(int j=varNum-1; j>=0; j--){
            if(markingEx[j]==true){
                value = logic_invalid;
            }
            else{
                value = tupleList[listLenL + i]->GetValueAt(j);
            }
            tupleR[i]->SetValueAt(j,value);
        }
//        tupleR[i]->print();
    }

    
//    ==========================================================================
//    FINDS THE LENGTH OF THE CHILD'S G-FUNCTION
//    ==========================================================================
    int childGLen = this->GetGFunc()->GetTupleLength()>>1;
//    cout << "G1-Len: " <<this->GetGFunc()->GetTupleLength()<<": ";
//    cout << listLenL << ":" << listLenR << ":";this->GetGFunc()->print();
//    cout << "Shifted G>>"<< childGLen <<": ";  (*gFunc>>childGLen)->print();
    if(listLenL > 0){
        BNode* nextNodeL = new BNode(varNum);
        nextNodeL->SetNodeName("left");
        this->SetChildL(nextNodeL);
        
//        gl->print();
    }
    if(listLenL>1){
        this->GetChildL()->process0(tupleL,listLenL);
        TupleK* gl = new TupleK(childGLen);
        gl->setTuple(*gFunc>>childGLen);
        childL->SetGFunc(gl);
    }
    else if(listLenL==1){
        this->GetChildL()->SetTuple(*tupleL);
        this->GetChildL()->GetGFunc()->setTuple(logic_invalid);
    }

    if(listLenR>0){
        BNode* nextNodeR = new BNode(varNum);
        nextNodeR->SetNodeName("right");
        this->SetChildR(nextNodeR);
        
//        gr->print();
    }
    if(listLenR>1){
        this->GetChildR()->process0(tupleR,listLenR);
        TupleK* gr = new TupleK(childGLen);
        gr->setTuple(gFunc);
        childR->SetGFunc(gr);
    }
    else if(listLenR==1){
        this->GetChildR()->SetTuple(*tupleR);
        this->GetChildR()->GetGFunc()->setTuple(logic_invalid);
    }
    
    for(int j=1; j< listLenL; j++){
        delete tupleL[j];
    }
//    delete[] tupleL;
    for(int j=1; j< listLenR; j++){
        delete tupleR[j];
    }
//    delete[] tupleR;
}

bool BNode::checkFor1(){
    TupleK* l = GetChildL()->GetGFunc();
    TupleK* r = GetChildR()->GetGFunc();
////    ==========================================================================
////    CHECKING FOR a+a'=1
////    ==========================================================================
    int c=0, xcare;
//    bool pairNot1 = false;
//    bool singleBit = true;
//    for(int i=r->GetTupleLength()-1; i>=0; i--){
////        ======================================================================
////        WE SKIP THE POSITIONS IN EITHER TUPLES THAT HAVE INVALID (-) BIT
////        ======================================================================
//        if((r->GetValueAt(i) == logic_invalid) && (l->GetValueAt(i) == logic_invalid)){
//            continue;
//        }
////        ======================================================================
////        REPORTING THAT THE TUPLES ARE NOT FOLLOWING SAME PATTERN
////        THUS THEY ARE NOT INVERSE OF EACH OTHER
////        ======================================================================
//        if((r->GetValueAt(i) == logic_invalid) || (l->GetValueAt(i) == logic_invalid)){
//            pairNot1=true;
//            break;
//        }
////        ======================================================================
////        COUNTING THE NUMBER OF DIFFERENT BITS
////        ======================================================================
//        if(r->GetValueAt(i) != l->GetValueAt(i)){
//            c++;
//            xcare = i;
//        }
//        else{
//            singleBit = false;
//        }
//    }
//
////    ==========================================================================
////    THERE SHOULD BE ONE AND ONLY ONE DIFFENT BIT IN THE TUPLE
////    ==========================================================================
//    if(!pairNot1 && c==1){
//        if(singleBit){
////            removeChildren();
//        }
//        else{
//            l->SetValueAt(xcare, logic_invalid);
//            r->setTuple(logic_invalid);
//        }
//        return true;
//    }
//    return false;

    if(*l == r){
        l=childL->GetTuple();
        r=childR->GetTuple();
//        l->print();
//        r->print();
        for(int i=0; i< l->GetTupleLength(); i++){
            if(l->GetValueAt(i) != r->GetValueAt(i)){
                xcare = i;
                c++;
            }
        }

        if(c==1){
//            cout << "equal to 1: " << xcare << endl;
//            l->print();
            l->SetValueAt(xcare, logic_invalid);
            r->SetValueAt(xcare, logic_invalid);
//            l->print();
            childL->setFUpdated(true);
            childR->setFUpdated(true);
            return true;
        }
    }
    return false;
}

bool BNode::checkForXNor(){
//    cout << "checkForXor" << endl;
    bool isXor = false, isXnor = false, xor1 = true, xor2=true, xnor1 = true, xnor2=true;
    int bitCheck = 0, logicCounter=0;
    if(hasChildL() && hasChildR()){
        TupleK* l = GetChildL()->GetGFunc();
        TupleK* r = GetChildR()->GetGFunc();
//        tuple->print();
//        l->print();
//        r->print();
//        cout << "-----------------" << endl;
        if(!l->containsLogic() && !r->containsLogic()){
//            cout << "Here\n";
            l = GetChildL()->GetTuple();
            r = GetChildR()->GetTuple();
//            l->print();
//            r->print();
            for(int i=0;i<l->GetTupleLength();i++){
                if(l->GetValueAt(i) == logic_invalid ||
                        r->GetValueAt(i) == logic_invalid){
                    continue;
                }
                else{
                    logicCounter++;
                    if(xor1){
                        if((l->GetValueAt(i) == logic_0 && r->GetValueAt(i) == logic_1)){
                            xor2 = false;
                        }
                        if((l->GetValueAt(i) == logic_1 && r->GetValueAt(i) == logic_0)){
                            xor2 = true;
                        }
                        xor1 = false;
                    }
                    else if(!xor1){
                        if(xor2 && (l->GetValueAt(i) == logic_0 && r->GetValueAt(i) == logic_1)){
                            isXor = true;
                        }
                        if(!xor2 && (l->GetValueAt(i) == logic_1 && r->GetValueAt(i) == logic_0)){
                            isXor = true;
                        }
                    }
                    if(xnor1){
                        if((l->GetValueAt(i) == logic_0 && r->GetValueAt(i) == logic_1)){
                            xnor2 = false;
                        }
                        if((l->GetValueAt(i) == logic_1 && r->GetValueAt(i) == logic_0)){
                            xnor2 = true;
                        }
                        xnor1 = false;
                    }
                    else if(!xnor1) {
                        if(xnor2 && (l->GetValueAt(i) == logic_1 && r->GetValueAt(i) == logic_0)){
                            isXnor = true;
                        }
                        if(!xnor2 && (l->GetValueAt(i) == logic_0 && r->GetValueAt(i) == logic_1)){
                            isXnor = true;
                        }
                    }
                }
            }
            if(logicCounter == 2){
                if(isXor){
                    for(int i=0;i<l->GetTupleLength();i++){
                         if(r->GetValueAt(i) == logic_0)
                             r->SetValueAt(i, logic_invalid);
                         if(l->GetValueAt(i) == logic_0)
                             l->SetValueAt(i, logic_invalid);
                    }
                    this->operation = logic_xor;
                }
                else if(isXnor){
                    bool firstCheckR=true,firstCheckL=true;
//                    l->print();
//                    r->print();
                    for(int i=0;i<l->GetTupleLength();i++){
                         if(firstCheckR && (r->GetValueAt(i) == logic_1)){
                             firstCheckR = false;
                         }
                         else r->SetValueAt(i, logic_invalid);
                         if(firstCheckL && l->GetValueAt(i) == logic_0){
                             l->SetValueAt(i, logic_invalid);firstCheckL=false;
                         }
                         else if(!firstCheckL && l->GetValueAt(i) == logic_0)
                             l->SetValueAt(i, logic_1);
                    }
                    this->operation = logic_xnor;
                }
//                l->print();
//                r->print();
                childL->setFUpdated(true);
                childR->setFUpdated(true);
                
//                cout << "Applying Xor ..." << endl;
                return true;
            }
        }
        else{

        }
//        if(*l %= *r){
////            cout << "xnor" << endl;
//            this->operation = logic_xnor;
////            cout << "Applying xor"<< endl;
//            return true;
//        }
    }
    return false;
}

void BNode::applyRules(){
//    cout << this << " " <<nodeName << ": ";
//    tuple->print();
//    gFunc->print();
    if(!isMinimized){
        if(this->hasChildL() && this->hasChildR()){
            if(childL->isLeaf() && childR->isLeaf()){
//                tuple->print();
//                childL->GetTuple()->print();
//                childR->GetTuple()->print();
//                childL->GetGFunc()->print();
//                childR->GetGFunc()->print();
//                gFunc->print();
                if(checkFor1()){
//                    cout << "removed redundancy" << endl;
//                    childL->GetTuple()->print();
//                    childR->GetTuple()->print();
//                    gStrEmpty = true;
                    makeGFuncStr();
                    removeChildren();
//                    cout << nodeName << " : "<<*funcStr << endl;
                }
                else if(checkForXNor()){
                    makeGFuncStr();
                    removeChildren();
                }
                else{
                    makeGFuncStr();
                    removeChildren();
                }
                isMinimized = true;
            }
            else{
                if(childL){
                    childL->applyRules();
                }
                if(childR){
                    childR->applyRules();
                }
            }
//            cout << "Minimizing" << endl;
            if(parent!=NULL){
//                cout << "calling parent" << endl;
                parent->applyRules();
            }
        }
    }
//    else cout << nodeName << ": is already minimized" << endl;
}

void BNode::makeGFuncStr(){
    bool fl=false;
    bool fr=false;
    bool gl=false;
    bool gr=false;
    bool plus = false;
//    cout << nodeName << endl;
    stringstream fBuff("");
    stringstream gBuff("");
//    cout << "fUpdated: " << fUpdated << endl;
    if(this->isLeaf()&&gStrEmpty){
//        tuple->print();
        *funcStr = tuple->getFunction();
        *gFuncStr = "";        
//        cout << *funcStr << ":" << *gFuncStr << endl;
    }
    if(this->isLeaf()&&fUpdated){
        *funcStr = tuple->getFunction();
        fUpdated = false;
    }
    if(!this->isLeaf()){
        childL->makeGFuncStr();
        childR->makeGFuncStr();

        if(operation == logic_or){
            
            if(!childL->getFFuncStr()->empty()){
                gBuff << *childL->getFFuncStr();
            }
            if(!childL->getGFuncStr()->empty()){
                gBuff << "(";
                gBuff << *childL->getGFuncStr();
                gBuff << ")";
            }
            
            if(!childR->getFFuncStr()->empty()){
                gBuff << " + ";
                plus = true;
                gBuff << *childR->getFFuncStr();
            }
            if(!childR->getGFuncStr()->empty()){
                if(!plus){
                    gBuff << " + ";plus = true;
                }
                gBuff << "(";
                gBuff << *childR->getGFuncStr();
                gBuff << ")";
            }
        }
        else if (operation == logic_xor){
            if(!childL->getFFuncStr()->empty()){
                gBuff << *childL->getFFuncStr();
            }
            
            if(!childR->getFFuncStr()->empty()){
                gBuff << " * ";
//                gBuff << "(";
                gBuff << *childR->getFFuncStr();
//                gBuff << ")";
            }

//            gBuff << childL->GetTuple()->getFunction();
//            gBuff << " # ";
//            gBuff << childR->GetTuple()->getFunction();
        }
        else if (operation == logic_xnor){
            if(!childL->getFFuncStr()->empty()){
                gBuff << *childL->getFFuncStr();
            }

            if(!childR->getFFuncStr()->empty()){
                gBuff << " # ";
//                gBuff << "(";
                gBuff << *childR->getFFuncStr();
//                gBuff << ")";
            }

//            gBuff << childL->GetTuple()->getFunction();
//            gBuff << " # ";
//            gBuff << childR->GetTuple()->getFunction();
        }

//        cout << this->tuple->getFunction();
        string f(this->tuple->getFunction());
        fBuff << f;
//        if(!gBuff.str().empty()){
//            fBuff << "(";
//            fBuff << gBuff.str();
//            fBuff << ")";
//        }

        *funcStr = fBuff.str();
        *gFuncStr = gBuff.str();

    }
    gStrEmpty = false;
//    fUpdated = false;
//    cout << "G: " <<*gFuncStr << endl;
//    cout << "F: " <<*funcStr << endl;
}

char* BNode::getOperationStr(){
    if(operation == logic_xor)
        return (char*)" * ";
    else if(operation == logic_or)
        return (char*)" + ";
}

string* BNode::getGFuncStr(){
    return this->gFuncStr;
}

string* BNode::getFFuncStr(){
    return this->funcStr;
}

char* BNode::printSimplified(){
    if(!this->isLeaf()){
        makeGFuncStr();
    }
    return (char*)getGFuncStr()->c_str();
}

char* BNode::printFunction(){
    stringstream buff("");
    if(childL){
        buff << "(";
        buff << printChildL();
        buff << childL->printFunction();
    }

    if(childR){
        buff << getOperationStr();
        buff << printChildR();
        buff << childR->printFunction();
        buff << ")";
    }
    *gFuncStr = buff.str();
    return (char*)gFuncStr->c_str();
}

char* BNode::printChildL(){
    return childL->GetTuple()->getFunction();
}

char* BNode::printChildR(){
    return childR->GetTuple()->getFunction();
}